from leetcode_test import *


class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        levels = []

        if not root:
            return []

        def helper(node: TreeNode, level: int):
            if len(levels) == level:
                levels.append([])

            if level % 2 == 0:

                levels[level].append(node.val)
            else:
                levels[level].insert(0, node.val)


            if node.left:
                helper(node.left, level + 1)
            if node.right:
                helper(node.right, level + 1)

        helper(root, 0)
        return levels


def test():
    t = TreeNode.create([3, 9, 20, None, None, 15, 7])
    assert Solution().zigzagLevelOrder(t) == [[3], [20, 9], [15, 7]]


def test2():
    t = TreeNode.create([1, 2, 3, 4, None, None, 5])
    assert Solution().zigzagLevelOrder(t) == [[1], [3, 2], [4, 5]]


if __name__ == "__main__":
    t = TreeNode.create([1, 2, 3, 4, 5, 6, 7, 8, 9, 0])
    print(Solution().zigzagLevelOrder(t))
